package wxy;

import java.util.Arrays;

public class LeetCode654 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            if (nums == null) {
                return null;
            }
            int n = nums.length;
            if (n == 0) {
                return null;
            }
            int maxIdx = -1;
            int max = -1;
            for (int i = 0; i < n; i++) {
                if (nums[i] > max) {
                    max = nums[i];
                    maxIdx = i;
                }
            }
            TreeNode treeNode = new TreeNode(max);
            treeNode.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, maxIdx));
            treeNode.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, maxIdx + 1, n));
            return treeNode;
        }
    }

}
